package com.exercises;

//缺失的第一个正数
class Exercise41 {
    public static void main(String[] args) {
        System.out.println(new Exercise41().firstMissingPositive(new int[]{1, 1}));
    }


    public int firstMissingPositive(int[] nums) {
        //一个N长度的数组  缺失正数的范围一定在1~N+1之间
        //先将数组里负数转成正数 随便取一个大于N的值
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = nums.length + 1;
            }
        }

        //标记数字是否出现 num[x]=a则num[a-1]取负值
        //例子 num[5]=1 则num[0]的值取反
        for (int i = 0; i < nums.length; i++) {
            int value = Math.abs(nums[i]);
            if (value <= nums.length) {
                nums[value - 1] = 0 - Math.abs(nums[value - 1]);
            }
        }

        //如果数组x位置为负值,表示x+1这个值出现过
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}
